/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums: number[]) {

    const ans: number[][] = []

    nums.sort((a, b) => a - b)

    function sum(a: number[]): number {
        return a.reduce((s, a) => s + a, 0)
    }

    const equal = (a: any[], b: any[]) => a.every((item, index) => b[index] === item)

    const biSearch = (from: number, target: number) => {
        let beg = from, end = nums.length - 1

        while (beg <= end) {
            const mid = Math.floor((beg + end) / 2)

            if (nums[mid] === target) {
                return mid
            }

            if (nums[mid] > target) {
                end = mid - 1
            } else {
                beg = mid + 1
            }
        }

        return -1

    }


    let container: number[] = []

    function search(from: number) {
        // console.log(container, sum(container))

        if (sum(container) > 0) return

        if (container.length === 3) {

            if (sum(container) === 0) {

                if (ans.every(a => !equal(a, container))) {
                    ans.push(container.slice())
                }

            }
            return
        }

        if (from === nums.length) {
            return
        }

        if (container.length === 2 && sum(container) <= 0) {
            // bi search
            const next = biSearch(from, -sum(container))

            if (next >= from) {
                container.push(nums[next])
                search(next + 1)
                container.pop()
            }

            return
        } else {

            container.push(nums[from])
            search(from + 1)
        }

        container.pop()
        let next = from + 1
        search(next)
    }

    search(0)

    // console.log('a', ans)
    // console.log(nums)

    return ans
};


// threeSum([0, 0, 0])
threeSum([-1, 0, 1, 2, -1, -4]);
;
